package com.yoshino.leetcode.interview150.list;

import java.util.HashMap;
import java.util.Map;

/**
 * Definition for singly-linked list.
 * class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        // 快慢指针
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0), cur = root;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int l1val = l1 == null ? 0 : l1.val;
            int l2val = l2 == null ? 0 : l2.val;
            int sum = l1val + l2val + carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        return root.next;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode root = new ListNode(0), cur = root;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                cur.next = list2;
                list2 = list2.next;
            } else {
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
        if (list1 != null) {
            cur.next = list1;
        }
        if (list2 != null) {
            cur.next = list2;
        }
        return root.next;
    }

    public Node copyRandomList(Node head) {
        // 先复制一次，再复制random和next
        if (head == null) {
            return head;
        }
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        while (cur != null) {
            Node clone = new Node(cur.val);
            map.put(cur, clone);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }
        ListNode root = new ListNode(0), cur = root;
        root.next = head;
        int i = 0;
        // 找到待转入的前一节点
        while (++i < left) {
            cur = cur.next;
        }
        ListNode first = cur.next, second = first.next, temp;
        // 反转中间的部分
        while (i++ < right) {
            temp = second.next;
            second.next = first;
            first = second;
            second = temp;
        }
        // 将边沿两边的节点进行next修改
        temp = cur.next;
        cur.next = first;
        temp.next = second;
        return root.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }
        ListNode root = new ListNode(0), cur = root;
        root.next = head;
        while (true) {
            // cur 作为 起始节点的上一个节点，不参与反转
            ListNode first = cur;
            for (int i = 0; i < k; i++) {
                first = first.next;
                if (first == null) {
                    // 不够反转，直接返回
                    return root.next;
                }
            }
            ListNode start = head, end = first.next, temp, tail = end;
            while (start != end) {
                temp = start.next;
                start.next = tail;
                tail = start;
                start = temp;
            }
            cur.next = first;
            cur = head;
            head = head.next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 先判断长度，利用双指针，快慢
        ListNode first = new ListNode(0), second = first;
        first.next = head;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        // 一起走
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        if (head == second.next) {
            // 移除头节点
            head = head.next;
        } else {
            second.next = second.next.next;
        }
        return head;
    }

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode root = new ListNode(0), pre = root, cur = head;
        root.next = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                // 有重复
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return root.next;
    }

    public ListNode rotateRight(ListNode head, int k) {
        // 翻转链表
        if (k == 0) {
            return head;
        }
        int length = 0;
        ListNode root = new ListNode(0), tail, temp = root;
        root.next = head;
        while (temp.next != null) {
            length++;
            temp = temp.next;
        }
        if (length < 2 || k % length == 0) {
            return head;
        }
        k = k % length;
        tail = temp;
        temp = head;
        for (int i = 1; i < length - k; i++) {
            temp = temp.next;
        }
        root.next = temp.next;
        tail.next = head;
        temp.next = null;
        return root.next;
    }

    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode root = new ListNode(0), first = root;
        ListNode root2 = new ListNode(0), second = root2;
        while (head != null) {
            if (head.val < x) {
                first.next = head;
                first = first.next;
            } else {
                second.next = head;
                second = second.next;
            }
            head = head.next;
        }
        second.next = null;
        first.next = root2.next;
        return root.next;
    }
}